package com.sheng.leetcode.year2022.swordfingeroffer.day27;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/09/26
 *<p>
 * 剑指 Offer 59 - I. 滑动窗口的最大值<p>
 *<p>
 * 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。<p>
 *<p>
 * 示例:<p>
 * 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3<p>
 * 输出: [3,3,5,5,6,7]<p>
 * 解释:<p>
 *<p>
 *   滑动窗口的位置                最大值<p>
 * ---------------               -----<p>
 * [1  3  -1] -3  5  3  6  7       3<p>
 *  1 [3  -1  -3] 5  3  6  7       3<p>
 *  1  3 [-1  -3  5] 3  6  7       5<p>
 *  1  3  -1 [-3  5  3] 6  7       5<p>
 *  1  3  -1  -3 [5  3  6] 7       6<p>
 *  1  3  -1  -3  5 [3  6  7]      7<p>
 *<p>
 * 提示：<p>
 *<p>
 * 你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤nums.length。<p>
 *<p>
 * 注意：本题与主站 239 题相同：<a href="https://leetcode-cn.com/problems/sliding-window-maximum/">...</a><p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0059 {

    @Test
    public void test01() {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        System.out.println(Arrays.toString(new Solution().maxSlidingWindow(nums, k)));
    }
}
// 暴力破解，超时
//class Solution {
//    public int[] maxSlidingWindow(int[] nums, int k) {
//        List<Integer> list = new ArrayList<>();
//        int length = nums.length;
//        for (int i = 0; i <= length - k; i++) {
//            int max = Integer.MIN_VALUE;
//            for (int j = i; j < i + k; j++) {
//                max = Math.max(max, nums[j]);
//            }
//            list.add(max);
//        }
//        return list.stream().mapToInt(Integer::intValue).toArray();
//    }
//}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // n代表数组长度
        int n = nums.length;
        // 创建一个优先级队列
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        // 将数组nums的前k个元素放入优先级队列中，按照优先按照元素大小，从大到小排列，如果元素值相等，则按照索引index从大到小排列
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        // 返回数组
        int[] ans = new int[n - k + 1];
        // 将优先级队列的第一个元素取出，值放入结果数组的第一个位置
        ans[0] = pq.peek()[0];
        // 循环k以及k之后位置的元素
        for (int i = k; i < n; ++i) {
            // 同样将元素放入队列中
            pq.offer(new int[]{nums[i], i});
            // 如果队列的首元素的索引位置，小余最小值i - k
            while (pq.peek()[1] <= i - k) {
                // 则将队列的首元素出栈
                pq.poll();
            }
            // 将符合的队列中的首元素放入结果数组中
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}
